/*
题目：从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
public class BuildTreeAA {
    Map<Integer, Integer> map = new HashMap<> ();
    int index = 0; //专门用于遍历中序数组

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < preorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(preorder, inorder, 0, preorder.length);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int start, int end) {
        if (start == end - 1) {
            index++;
            return new TreeNode(inorder[start]);
        } else if (start > end - 1) {
            return null;
        }

        TreeNode newNode = new TreeNode(preorder[index]); //确立根节点
        int mid = map.get(preorder[index]);  //获取根节点在前序数组中的下标
        index++;

        newNode.left = buildTree(preorder, inorder, start, mid);
        newNode.right = buildTree(preorder, inorder, mid + 1, end);

        return newNode;
    }
}
